package day_2022_4_to_7.nowcoder;

import java.util.HashMap;
import java.util.Map;

/**
 * 数组中只出现一次的数字
 * @author haomin
 * @date 2022/05/11 10:42
 **/
public class FindNumsAppearOnce_30f {
    // 方法一 异或^
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int result = 0;
        // 1.将所有元素全部异或一遍
        // 得到的result就是两个只出现一次的异或结果
        for(int i = 0;i < array.length;i++){
            result ^= array[i];
        }

        // 2. 找到整体异或结果其中为1的比特位（只有两个单身数字异或结果有1的比特位）
        int flag = 1;
        while (true){
            if((flag & result) != 0){
                break;
            }
            flag <<= 1;
        }

        // 3. 所以我们可以用该比特位进行分组，分组的结果一定是，
        // 相同数据被分到了同一组，不同数据一定被分到了不同的组，问题就转化成了两个问题一
        for (int i = 0; i < array.length; i++) {
            if((flag & array[i]) == 1){
                num1[0] ^= array[i];
            }else {
                num2[0] ^= array[i];
            }
        }
    }

    // 方法二 map
    public void FindNumsAppearOnce1(int [] array,int num1[] , int num2[]) {
        // 1. 先设置一个map集合，并将所有元素加入map集合中
        Map<Integer,Integer> map = new HashMap<>();
        for(int i : array){
            if(map.containsKey(i)){
                // 如果map中已存在该元素，使该value+1
                map.replace(i,map.get(i)+1);
            }else {
                map.put(i,1);
            }
        }
        // 2. 遍历map集合，其中value值为1 的元素就是单身元素
        int count = 0;
        for(int i : array){
            if(map.get(i) == 1){
                if(count == 0){
                    num1[0] = i;
                    count ++;
                }else {
                    num2[0] = i;
                }
            }
        }
    }
}